package com.stephen.data.linkedlist;

import java.util.Stack;

/**
 * @author: stephen
 * @create: 2020-01-30 14:21
 * @description: 单链表的反转,使用栈来实现
 */
public class ReverseLinkedListDemo {
    public static HeroNode head = new HeroNode(0,"","" );

    public static void main(String[] args) {
        HeroNode h1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode h2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode h3 = new HeroNode(3, "吴用", "智多星");
        HeroNode h4 = new HeroNode(4, "林冲", "豹子头");
        addByOrder(h1);
        addByOrder(h4);
        addByOrder(h3);
        addByOrder(h2);
        list();
        System.out.println("反转之后的链表,未改变链表结构---");
        reverseList(head);


    }

    // 使用栈,来反转打印链表
    public static void reverseList(HeroNode head) {
        if (head.next == null) {
            return;
        }

        Stack<HeroNode> stack = new Stack<HeroNode>();
        HeroNode cur = head.next;
        // 将链表所有节点压入栈中
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }

        // 出栈
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }



    // 先初始化一个头节点,不存储数据
    // 有序添加,根据编号的大小存储

    public static void addByOrder(HeroNode node) {

        // 头节点不能动,故需要一个辅助指针来找到需要添加的位置
        // 单链表,我们需要找到添加位置的前一个节点,否则无法插入
        HeroNode temp = head;
        boolean flag = false; // 是否已经存在
        while (true) {
            if (temp.next == null) {
                // temp已在链表最后
                break;
            }
            if (temp.next.no > node.no) {
                // 说明找到正确的位置了,就在temp的后边插入
                break;
            } else if (temp.next.no == node.no) {
                flag = true; // 说明编号已存在
                break;
            }
            temp = temp.next; // 后移,遍历当前链表
        }

        if (flag) {
            System.out.printf("准备插入的编号[%d]已存在,无法插入\n",node.no);
        } else {
            // 新的元素,插入到temp的后边
            node.next = temp.next;
            // temp指向新的元素
            temp.next = node;
        }

    }

    // 链表的遍历
    public static void list() {
        if (head.next == null) {
            System.out.println("链表为空---");
            return;
        }
        HeroNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            // 后边还有元素,就输出元素
            System.out.println(temp);
            // 之后,把节点后移一位
            temp = temp.next;
        }

    }

}
